今日題目

題目：414. Third Maximum Numbe
題目主題：Array, Sorting

我會從最基本的排序開始，本題先不講任何演算法或資料結構。但我想在今天的這個題目來分享一下，我平常做題目時常使用介面上哪些區塊。

簡單說說 LeetCode解題介面

做題目的介面如下圖：

基本的操作不多做說明，但這邊想分享的是我平常做題目時常會使用到的幾個區塊：

1. 題目說明
   
   這是不看不行的地方，這個區塊在講的是這個題目的目標。
2. 題目範例
   
   題目範例，是會給你幾個Testcase讓你更了解題目的目標，稍微列幾種不同狀況出來。這邊特別說是因為，這邊會列出來的範例不一定是所有狀況，只是參考，思考題目時不要被這邊的範例綁住，要多思考有沒有不同狀況的可能性。
3. 題目約束
   
   這個約束的條件，非常重要，像這一題就有提到說不會出現nums裡面為空的狀態，至少都會有一個數字，往後的題目建議都要習慣先看一下，了解整個題目的限制範圍在哪，會對解題很有幫助。
4. Related Topics
   
   雖然在選題時，大概就會知道了，但通常我還是會再確認一下題目的主題，幫助自己思考解題的方向。
5. Testcase
   
   這邊想特別說的是，Use Example Testcases，點擊後會直接幫你把題目範例全部列出來，Run Code時會一次跑所有範例，滿方便的。如果想自己多增加幾個Testcase，也可以直接換行再增加自己想要的Testcase。
6. Run Code Result
   
   平常只會顯示Your input(輸入的Testcases)、Output(現在程式碼的輸出)、Expected(正確的輸出)這三個區塊。但如果在程式碼中，打上print('xxx')是可以印出來的 (因為是Python所以是使用print) ，會出現一個區塊叫stdout，如下圖。
   
   如果需要debug時，我自己會用這個方式來確認資料目前的狀況。

題目解說

建議可以看看LeetCode原本的題目說明，這邊是用我的方式說明題目，參考就好。

本題的目標是在一個nums的所有數字中，過濾掉相同的數字以後，找到第三大的數字。如果最終過濾完相同的數字後剩下數字不到三個，直接回傳最大的數字。

約束：

• 1 <= nums.length <= 104
• -231 <= nums[i] <= 231 - 1

範例1

輸入：nums = [3,2,1]
輸出：1
解釋：這是基本範例，數字各一個，直接找到第三大的數字回傳即可。

範例2

輸入：nums = [1,2]
輸出：2
解釋：數字不到三個，直接輸出最大的數字。

範例3

輸入：nums = [2,2,3,1]
輸出：1
解釋：過濾完重複的數字後會剩3、2、1，因此第三大的數字為1。

建議到這邊先停下來，嘗試自己解解看，若沒有想法可再繼續走下去。

解題的想像

文字描述

1. 宣告三個變數，分別為第一、第二、第三大的數字。
2. 跑一個迴圈，將nums中每個數字跑過一次。
3. 每個數字需檢查幾種狀況：
   • 數字已經出現過，直接略過。
   • 比第一位置的數字還大，取代第一大的數字。
   • 比第二位置的數字還大，取代第二大的數字。
   • 比第三位置的數字還大，取代第三大的數字。
   • 比第三位置的數字還小的數字，直接略過。
   • 檢查的位置沒值時，直接將數字放在此位置。
4. 若有取代數字的行為發生，要先將當前的值都往後退一個。
5. 若第三大數字沒值時，回傳第一大位置數字。
6. 若第三大數字有值時，回傳第三大數字。

圖解過程

範例：nums = [3, 3, 4, 2, 1, 5]

1. 宣告三個變數，分別為第一、第二、第三大的數字。
   
2. 第一輪 3直接放在第一個位置 / 第二輪 3出現過直接略過。
   
3. 第三輪 4比3大，將3往後推一個位置，將4放到第一大位置。
   
4. 第四輪 2小於3跟4，第三位置還沒值，直接放在第三位置。
   
5. 第五輪 1小於第三大的2，直接略過，不處理。
   
6. 第六輪 5大於目前第一大的4，將目前的值都往後推一個，將5放在第一個位置。
   
7. 最終因第三大位置有值，輸出數字為 3。
   

若因為沒想法而走到這邊，建議看完想像以後再給自己一次機會試一次。

程式碼撰寫

class Solution:
    def thirdMax(self, nums: List[int]) -> int:
        # 宣告三個變數，分別為第一、第二、第三大的數字
        first = nums[0] # 可以直接先把nums中第一個數字給最大的位置
        second = None 
        third = None
        # 因已經先取出第一個數字放在第一大的位置了，因此從nums中第二個數字開始走
        for i in range(1, len(nums)):
            # 過濾相同的數字，出現過數字的不處理
            if nums[i] == first or nums[i] == second or nums[i] == third:
                continue
            # 如果現在數字比第一個大，讓第一、第二數字往後退到第二、第三的位置以後
            # 再將數字放在第一大的位置
            if first < nums[i]:
                third = second
                second = first
                first = nums[i]
                continue
            # 如果現在數字比第二個大，第一位置不動
            # 第二位置數字移到第三位置，再將數字放在第二大的位置
            if second == None or second < nums[i]:
                third = second
                second = nums[i]
                continue
            # 如果現在數字比第三個大，第一、第二位置不動
            # 直接將第三數字換成現在的值
            if third == None or third < nums[i]:
                third = nums[i]
                continue
        # 如第三位置有值，直接回傳第三大數字
        # 如第三位置沒有值，代表過濾完不到三個數字，回傳最大數字
        return third if third != None else first

希望您今天能瞭解到...

1. LeetCode解題介面我常會關注的部分
2. 414 . Third Maximum Number 解題方法

若內容有什麼問題或建議歡迎一起交流：）
感謝您今天願意花時間看完這篇文章~~~~

Next：747. Largest Number At Least Twice of Others